#ifndef xpack_algo_longest_common_substring
#define xpack_algo_longest_common_substring
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::algo_longest_common_substring::inc
#include"configure/limit.hpp"
#include"interface/can_alloc_seq.hpp"
#include"interface/unified_seq.hpp"
#include"macro/xdefer.hpp"
#include"macro/xexport.hpp"
#include"macro/xstruct.hpp"
#include"macro/xunlikely.hpp"
#include"utils/memory.hpp"
#include"utils/static_length_of.hpp"
#pragma pop_macro("xuser")

namespace mixc::algo_longest_common_substring{
    xstruct(
        xname(lcs_pair),
        xprif(m_index, uxx),
        xprif(m_length, uxx)
    )
        xprops()
            // 公共串在主串的起始位置
            xpubget_pubset(index, uxx);

            // 公共串的长度
            xpubget_pubset(length, uxx);
        $

        xprops_operator()

        template<class seq_main_t, class seq_pattern_t, class alloc_t>
        friend lcs_pair longest_common_substring_core(
            seq_main_t      const &,
            seq_pattern_t   const &,
            alloc_t         const &
        );
    $

    template<class seq_main_t, class seq_pattern_t, class alloc_t>
    inline lcs_pair longest_common_substring_core(
        seq_main_t      const & main, 
        seq_pattern_t   const & pattern,
        alloc_t         const & alloc
    ){
        auto main_length            = uxx(main->length);
        auto pattern_length         = uxx(pattern->length);
        auto result                 = lcs_pair{ };
        result->index               = not_exist;
        result->length              = 0;

        if (main_length == 0 or pattern_length == 0){
            return result;
        }

        if (pattern_length == 1){
            for(uxx i = 0; i < main_length; i++){
                if (main[i] == pattern[0]){
                    result->index   = i;
                    result->length  = 1;
                    return result;
                }
            }
            return result;
        }

        auto buffer                 = alloc(main_length);
        auto max_com                = uxx{};

        xunlikely(buffer->length == zero){
            return result;
        }

        for(uxx i = 0; i < main_length; i++){
            buffer[i]               = 0;
        }

        for(uxx i = 0; i < pattern_length; i++){
            for(uxx j = main_length; j-- > 0; ){
                if (pattern[i] != main[j]){
                    buffer[j]       = 0;
                    continue;
                }

                xunlikely(j == 0){
                    buffer[j]       = 1;
                }
                else{
                    buffer[j]       = buffer[j - 1] + 1;
                }

                if (max_com < buffer[j]){
                    result.m_index  = j;
                    max_com         = buffer[j];
                }
            }
        }

        if (result.m_length = max_com; result.m_index > 0){
            result.m_index         -= max_com - 1;
        }
        return result;
    }

    template<
        inc::can_unified_seqlize seq_main_t, 
        inc::can_unified_seqlize seq_pattern_t = seq_main_t,
        class alloc_t
    >
    requires(inc::can_alloc_seqx<alloc_t, uxx>)
    inline lcs_pair longest_common_substring(
        seq_main_t      const & main, 
        seq_pattern_t   const & pattern,
        alloc_t         const & alloc
    ){
        auto seq_main               = inc::unified_seq<seq_main_t>(main);
        auto seq_pattern            = inc::unified_seq<seq_main_t>(pattern);
        auto allocx                 = inc::can_alloc_seq_helper(alloc);
        return longest_common_substring_core(seq_main, seq_pattern, allocx);
    }

    template<
        inc::can_unified_seqlize seq_main_t, 
        inc::can_unified_seqlize seq_pattern_t = seq_main_t
    >
    inline lcs_pair longest_common_substring(
        seq_main_t      const & main, 
        seq_pattern_t   const & pattern
    ){
        uxx     buffer[inc::limit::algo_longest_common_substring];
        uxxp    heap_buffer     = nullptr;
        auto    bytes           = inc::memory::size{};

        xdefer{
            if (heap_buffer){
                inc::memory::free(heap_buffer, bytes);
            }
        };

        return longest_common_substring(main, pattern, [&](uxx length) -> uxxp {
            if (length < inc::static_length_of(buffer)){
                return buffer;
            }

            bytes               = xsizeof(uxx) * length;
            heap_buffer         = inc::memory::alloc<uxx>(bytes);
            return heap_buffer;
        });
    }
}
#endif

xexport(mixc::algo_longest_common_substring::longest_common_substring)
